package com.magic.interview.BFS.LC1765地图中的最高点;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author laoma
 * @create 2022-01-29 22:03
 */
public class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length;
        int n = isWater[0].length;
        int[][] ans = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    queue.add(new int[]{i, j});
                }
                ans[i][j] = isWater[i][j] == 1 ? 0 : -1;
            }
        }
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!queue.isEmpty()) {
            int[] top = queue.poll();
            int x = top[0];
            int y = top[1];
            for (int[] dir : dirs) {
                int a = x + dir[0];
                int b = y + dir[1];
                if (a < 0 || a >= m || b < 0 || b >= n) {
                    continue;
                }
                if (ans[a][b] != -1) {
                    continue;
                }
                ans[a][b] = ans[x][y] + 1;
                queue.add(new int[]{a, b});
            }
        }
        return ans;
    }
}
